package com.Offer;

/*
    面试题53：在排序数组中查找数字
    统计一个数字在排序数组中出现的次数。例如输入有序数组{1,2,3,3,3,3,4,5}和数组3，由于3在这个数组中出现了4次，所以输出4
 */
public class demo53 {
    public static void main(String[] args) {
        int[] data = {1,2,3,3,3,3,4,4,5};
        int first = GetFirstK(data, 5, 0, data.length - 1);
        int last = GetLastK(data, 5, 0, data.length - 1);
        System.out.println(last-first+1);

        int[] data1 = {0,1,2,3,4,5,7,8,9,10,11};
        System.out.println(GetMissingNumber(data1,0,data.length-1));

    }

    //利用二分查找获得数字出现的第一个位置
    public static int GetFirstK(int[] data,int k,int start,int end){
        if(start > end)
            return -1;
        int mid = (start+end)/2;
        int midData = data[mid];
        if(midData == k){
            if (mid > 0 && data[mid-1] != k || mid == 0){
                return mid;
            }else{
                end = mid-1;
            }
        }else if(midData > k){
            end = mid-1;
        }else{
            start = mid+1;
        }
        return GetFirstK(data,k,start,end);
    }

    //利用二分查找获得数字的最后一个位置
    public static int GetLastK(int[] data,int k,int start,int end){
        if (start > end)
            return -1;
        int mid = (start+end)/2;
        int midData = data[mid];
        if(midData == k){
            if(mid < data.length-1 && data[mid+1] != k || mid == data.length-1){
                return mid;
            }else {
                start = mid+1;
            }
        }else if(midData > k){
            end = mid-1;
        }else{
            start = mid+1;
        }


        return GetLastK(data,k,start,end);
    }

    //举一反三：0~n-1中缺失的数字，在长度为n-1的递增数组中所有数字都是唯一的，在这些数字中，找到缺失的数字
    public static int GetMissingNumber(int[] data,int start,int end){
        if (data == null || data.length == 0)
            return -1;
        while(start <= end){
            int mid = (start+end)/2;
            if (data[mid] == mid){
                start = mid+1;
            }else if(data[mid] != mid){
                if(mid > 0 && data[mid-1] != mid || mid == 0){
                    return mid;
                }else{
                    end = mid-1;
                }
            }
        }
        return -1;
    }


}
